LG1967【NOIp2013】货车运输 < MST+LCA >

Problem

货车运输

题目描述

国有座城市，编号从到，城市之间有条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：
输入文件名为。
输入文件第一行有两个用一个空格隔开的整数 , ，表示国有座城市和条道路。接下来行每行个整数、、，每两个整数之间用一个空格隔开，表示从号城市到号城市有一条限重为的道路。注意：不等于，两座城市之间可能有多条道路。
接下来一行有一个整数，表示有辆货车需要运货。
接下来行，每行两个整数、，之间用一个空格隔开，表示一辆货车需要从城市运输货物到城市，注意：不等于。
输出格式：
输出文件名为。
输出共有行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出。

输入输出样例

输入样例：

输出样例：

1
2
3

3
-1
3

说明

对于的数据，，，；
对于的数据，，，；
对于的数据，，，，。

标签：MST LCA

Solution

经典例题。
为了使得货车走过的路径上最小权最大，又要使其能到任意两点，那么该图可以缩减成一棵树，为了保证最优解，该树采用原图的最大生成树。
对于一次询问，在最大生成树上跑两点的，倍增统计路径最小值即可。
不错的板题

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX_N 10000
#define MAX_M 50000
#define INF 2147483647
using namespace std;
int n, m, q, cnt;
int first[MAX_N+5], d[MAX_N+5], p[MAX_N+5][15], f[MAX_N+5][15];
int father[MAX_N+5];
bool vis[MAX_N+5];
struct Edge {
    int from, to, c, next;
};
Edge G[MAX_M], edge[MAX_M+5];
inline int read() {
    int ret = 0;    char ch = getchar();
    while (ch < '0' || ch > '9')    ch = getchar();
    while (ch >= '0' && ch <= '9')    ret = ret*10+ch-'0', ch = getchar();
    return ret;
}
bool cmp (const Edge &a, const Edge &b) {
    return a.c > b.c;
}
void Add(int u, int v, int x) {
    cnt++;
    edge[cnt].to = v;
    edge[cnt].c = x;
    edge[cnt].next = first[u];
    first[u] = cnt;
}
int get_father(int cur) {
    if (father[cur] != cur)    father[cur] = get_father(father[cur]);
    return father[cur];
}
void Kruskal() {
    sort(G, G+m, cmp);
    for (int i = 1; i <= n; i++)    father[i] = i;
    for (int i = 0; i < m; i++) {
        int u = get_father(G[i].from), v = get_father(G[i].to);
        if (u != v) {
            father[u] = v;
            Add(G[i].from, G[i].to, G[i].c);
            Add(G[i].to, G[i].from, G[i].c);
        }
    }
}
void DFS(int u) {
    vis[u] = true;
    for (int i = 1; (1<<i) <= d[u]; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
        f[u][i] = min(f[u][i-1], f[p[u][i-1]][i-1]);
    }
    for (int i = first[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!vis[v]) {
            d[v] = d[u]+1;
            p[v][0] = u;
            f[v][0] = edge[i].c;
            DFS(v);
        }
    }
}
int LCA(int a, int b) {
    int ret = INF, i, j;
    if (d[a] < d[b])    swap(a, b);
    for (i = 0; (1<<i) <= d[a]; i++) {}    i--;
    for (j = i; j >= 0; j--) {
        if (d[a]-(1<<j) >= d[b]) {
            ret = min(ret, f[a][j]);
            a = p[a][j];
        }
    }
    if (a == b)    return ret;
    for (j = i; j >= 0; j--) {
        if (p[a][j] != p[b][j]) {
            ret = min(ret, min(f[a][j], f[b][j]));
            a = p[a][j];
            b = p[b][j];
        }
    }
    return min(ret, min(f[a][0], f[b][0]));
}
int main() {
    memset(f, 127, sizeof(f)); 
    n = read(), m = read();
    for (int i = 0; i < m; i++) {
        G[i].from = read(), G[i].to = read(), G[i].c = read();
    }
    Kruskal();
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && father[i] == i) {
            DFS(i);
        }
    }
    q = read();
    for (int i = 0; i < q; i++) {
        int a, b;
        a = read(), b = read();
        if (get_father(a) != get_father(b)) {
            printf("-1\n");
        } else {
            printf("%d\n", LCA(a, b));
        }
    }
    return 0;
}